//
// Created by francklinson on 2021/7/25 AT 9:44.
//

/**
给你一个字符串 s，找出它的所有子串并按字典序排列，返回排在最后的那个子串。
 */

#include <string>
#include <iostream>
#include <stack>

using namespace std;

class Solution {
public:
    /**
     * 1、如果已有一个i到j的子字符串，那么i到j+1必定是一个更好的结果  所以一定是包含字符串末尾的
     * 2、开头如何确定：首先一定是最大的那个字母   其次，如果有多个这样的字母 如何选择？
     *
     * 双指针，指针l记录字典序最大子串的首位下标，指针r向后扫描并与指针l进行比较
        s[l] > s[r]：r指针后移
        s[l] < s[r]：存在更大的子串，l移动到r，r指针后移
        s[l] == s[r]：k = 1,2,3,....，此时比较s[l + k] 与 s[r + k]，直到出现两者不相等的情况
        s[l + k] < s[r + k]: l移动到r，r指针后移
        s[l + k] > s[r + k]: l不动，r移动到r + k + 1

     * @param s
     * @return
     */
    string lastSubstring(string s) {
        int left = 0, right = 1, k = 0, n = s.size();
        while (right + k < n) {
            // 仅在发生相等的情况下，k不等于0
            if (s[left + k] == s[right + k]) ++k; // 相等
            else if (s[left] < s[right + k]) {  // 发现一个更大的开头
                left = right + k;
                right = left + 1;
                k = 0;
            } else if (s[left + k] < s[right + k]) { // right段更大
                left = right;
                ++right;
                k = 0;
            } else {  // left处的字符最大  right右移
                ++right;
                k = 0;
            }
        }
        return s.substr(left);
    }
};

class Solution2 {
public:
    string lastSubstring(string s) {
        string result = s;
        for (auto i = s.begin() + 1; i != s.end(); i++) {
            if (*i <= *(i - 1)) {
                continue;
            }
            if (lexicographical_compare(result.begin(), result.end(), i, s.end())) { // 比较字符串字典序 接受四个迭代器
                result = s.substr(i - s.begin());
            }
        }
        return (string) result;
    }
};

int main() {
    Solution2 solution;
    cout << solution.lastSubstring("abab") << endl;
    return 0;
}

